\begin{frame}
\frametitle{Motivation}

We try to find a definition for ``regular'' 2d languages, with following criteria

\begin{itemize}
	\item Adaption of definitions from string languages
	\item Different characterisations (automata, grammars etc. )
	\item Convenient closure properties, like for string languages
	\item Easy to distinguish, if a language is of this type or not
	\item The usual decision problems should be easy to solve
\end{itemize}

\end{frame}

\begin{frame}
\frametitle{Local languages}

\begin{define}[Local language \cite{cherubini2009picture}]

A language $L \subseteq \Sigma^{**}$ is local, if there exists a finite set $\Theta$ of tiles, where

\begin{itemize}
	\item a tile is a picture of size $(2, 2)$ over $\Sigma \cup \{\#\}$
	\item For any $p \in L$: $B_{2, 2}(p) \subseteq \Theta$
\end{itemize}

\end{define}

$LOC(\Theta)$ is the set of finite pictures bordered by \#'s and with a valid tiling. 

\end{frame}

\begin{frame}
\frametitle{Example}

\setlength{\tabcolsep}{4pt}
\begin{Example}
	\label{example_loc}
	\begin{align*} \Theta = \left\lbrace
	\begin{tabular}{c}
	\begin{tabular}{|c|c|}
	\hline
	\# & \# \\
	\hline
	\# & 1 \\
	\hline
	\end{tabular} ,
	\begin{tabular}{|c|c|}
	\hline
	1 & \# \\
	\hline
	\# & \# \\
	\hline
	\end{tabular}, 
	\begin{tabular}{|c|c|}
	\hline
	\# & \# \\
	\hline
	0 & \# \\
	\hline
	\end{tabular},
	\begin{tabular}{|c|c|}
	\hline
	\# & 0 \\
	\hline
	\# & \# \\
	\hline
	\end{tabular}, 
	\text{      }
	\begin{tabular}{|c|c|}
	\hline
	\# & 1 \\
	\hline
	\# & 0 \\
	\hline
	\end{tabular}, 
	\begin{tabular}{|c|c|}
	\hline
	\# & 0 \\
	\hline
	\# & 0 \\
	\hline
	\end{tabular}, 
	\begin{tabular}{|c|c|}
	\hline
	0 & \# \\
	\hline
	0 & \# \\
	\hline
	\end{tabular}, 
	\begin{tabular}{|c|c|}
	\hline
	0 & \# \\
	\hline
	1 & \# \\
	\hline
	\end{tabular}\\[2ex]
	\begin{tabular}{|c|c|}
	\hline
	0 & 0 \\
	\hline
	\# & \# \\
	\hline
	\end{tabular}, 
	\begin{tabular}{|c|c|}
	\hline
	0 & 1 \\
	\hline
	\# & \# \\
	\hline
	\end{tabular}, 
	\begin{tabular}{|c|c|}
	\hline
	\# & \# \\
	\hline
	1 & 0 \\
	\hline
	\end{tabular}, 
	\begin{tabular}{|c|c|}
	\hline
	\# & \# \\
	\hline
	0 & 0 \\
	\hline
	\end{tabular}, 
	\text{      }
	\begin{tabular}{|c|c|}
	\hline
	1 & 0 \\
	\hline
	0 & 1 \\
	\hline
	\end{tabular}, 
	\begin{tabular}{|c|c|}
	\hline
	0 & 1 \\
	\hline
	0 & 0 \\
	\hline
	\end{tabular}, 
	\begin{tabular}{|c|c|}
	\hline
	0 & 0 \\
	\hline
	1 & 0 \\
	\hline
	\end{tabular}, 
	\begin{tabular}{|c|c|}
	\hline
	0 & 0 \\
	\hline
	0 & 0 \\
	\hline
	\end{tabular}
	\end{tabular}
	\right\rbrace
	\end{align*}
\end{Example}
\setlength{\tabcolsep}{6pt}

$LOC(\Theta) = \{p \in \{0, 1, \#\}^{**} \mid l_1(p) = l_2(p) \text{ and } p(i, i) = 1 \text{ and } p(i, j) = 0 \forall i, j \in \{1, \dots, l_1(p)\}, i \neq j\}$ is the language with pictures of squares, and 1's on the diagonal from top-left to bottom-right. 

\end{frame}

\begin{frame}
\frametitle{Tiling system}

\begin{define}[Tiling system \cite{cherubini2009picture}]
$T = (\Sigma, \Gamma, \Theta, \pi)$ is called tiling system (TS) where

\begin{itemize}
	\item $\Sigma$ and $\Gamma$ are two finite alphabets. 
	\item $\pi: \Gamma \rightarrow \Sigma$ is a mapping
	\item $\Theta$ is a finite set of $2 \times 2$ tiles over $\Gamma \cup \{\#\}$. 
\end{itemize}

\end{define}

$\mathcal{L}(TS)$ is the family of languages, which are recognizable by tiling systems. 

Note: The tiling system is creating a picture $\hat{p}$. The mapping is only using the picture p. 

\end{frame}

\begin{frame}
\frametitle{Example}

\begin{Example}
Let $T = (\Sigma, \Gamma, \Theta, \pi)$ be a tiling system with

\begin{itemize}
	\item $\Theta$ from example~\ref{example_loc}
	\item $\Gamma = \{0, 1\}$
	\item $\Sigma = \{a\}$
	\item $\pi(0) = \pi(1) = a$
\end{itemize}
\end{Example}

$L(T) = \{p \in \Sigma^{**} \mid l_1(p) = l_2(p)\}$ is the language with square size pictures over a. 

Another example is the language, containing square shaped pictures of size n with a solution for the n-Queens problem. 
	
\end{frame}

\begin{frame}
\frametitle{hv-local languages}

We can make some modifications, that we allow only tiles of size $(1, 2)$ or $(2, 1)$. We then speak about dominos. 

\begin{define}[hv-local languages]
	If L is a local language with $\Delta$ a set of dominos, L is called \emph{hv-local}. 
\end{define}

\begin{thm}
	The family of hv-local languages is properly included in the family of local languages. 
\end{thm}

\begin{proof}
	see \cite{Giammarresi1997}. 
\end{proof}

\end{frame}

\begin{frame}
\frametitle{Domino systems}
\begin{define}[Domino system \cite{Giammarresi1997}]
$T = (\Sigma, \Gamma, \Delta, \pi)$ is called domino system (DS) where

\begin{itemize}
	\item $\Sigma$ and $\Gamma$ are two finite alphabets. 
	\item $\pi: \Gamma \rightarrow \Delta$ is a mapping
	\item $\Delta$ is a finite set of dominos. 
\end{itemize}

\end{define}

$\mathcal{L}(DS)$ is the family of languages recoqnized by domino systems. In general, this class of languages is called the class of recognizable picture languages (REC). 

\begin{thm}
	$\mathcal{L}(TS) = \mathcal{L}(DS) = REC$
\end{thm}
\end{frame}

\begin{frame}[allowframebreaks]
\frametitle{Generalization of local languages}

\begin{define}[local testable languages \cite{Giammarresi1997}]
Let $h, k \geq 1$ a pair of numbers. We define an equivalence relation on $\Sigma^{**}$ denoted by $\sim_{h, k}$ with 

$\forall p,q \in \Sigma^{**}:  p \sim_{h, k} q \Leftrightarrow B_{h,k}(\hat{p}) = B_{h, k}(\hat{q})$
\end{define}

That means, that two pictures are equivalent, if they have the same set of subpictures of size (h, k). 

\begin{define}
A two dimensional language L over $\Sigma$ is locally testable, if it is union over $\sim_{h, k}$-euqivalence classes for some h and k. 
\end{define}

The family of locally testable picture languages is denoted by LT. 

\pagebreak

As a further generalization, we can count the occurences of subpictures, which leads us to the following equivalence class (using $occ_p(q) = $ number of occurances of p in q): 

\begin{define}[local threshold testable languages \cite{Giammarresi1997}]
Let $h, k \geq 1$ a pair of numbers. We define an equivalence relation on $\Sigma^{**}$ denoted by $\sim_{h, k}$ with 

$\forall p,q \in \Sigma^{**}:  p \sim_{h, k} q \Leftrightarrow B_{h,k}(\hat{p}) = B_{h, k}(\hat{q})$ and $\forall p' \in B_{h,k}(\hat{p}), q' in B_{h, k}(\hat{q}): min(occ_{p'}(\hat{p}), t) = min(occ_{q'}(\hat{q}), t)$
\end{define}

\begin{define}
A two dimensional language L over $\Sigma$ is locally threshold testable, if it is union over $\sim_{h, k}^t$-euqivalence classes for some h, k and t. 
\end{define}

The family of locally threshold testable picture languages is denoted by LTT. 

\begin{thm}
$LT \subsetneq LTT \subsetneq REC$
\end{thm}

\end{frame}